package com.bootcamp.s2_0922.ds.Exercise._0923_ex1;

/**
 * @program: myClassCode
 * @description:
 * @author: Keyu Li
 * @create: 2021-09-23 19:38
 **/

public class Ex {
    public static void main(String[] args) {
        MyDBList list = new MyDBList();
        list.add("1");
        list.add(0, "0");
        list.add(2, "2");
        System.out.println(list);
    }
}

class MyDBList {
    class Node {
        String value;
        Node pre;
        Node next;

        public Node(String value, Node pre, Node next) {
            this.value = value;
            this.pre = pre;
            this.next = next;
        }

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Node{");
            sb.append("value='").append(value).append('\'');
            sb.append(", next=").append(next);
            sb.append('}');
            return sb.toString();
        }
    }

    private Node head;
    private Node rear;
    private int size;

    public MyDBList() {
    }

    // judge whether is empty
    public boolean isEmpty() {
        return size == 0;
    }

    // add new element
    public boolean add(String element) {
        // 判断当前链表是否为null
        if (isEmpty()) {
            // 如果为空，则新建链表，且头，尾
            head = new Node(element, null, null);
            rear = head;
            size++;
            return true;
        }
        // 如果非null，则在尾节点插入
        rear.next = new Node(element, rear, null);
        rear = rear.next;
        size++;
        return true;
    }

    // add index and element
    public boolean add(int index, String element) {
        // 判断当前链表是否为null
        if (isEmpty()) {
            // 如果为null，判断index是否为0
            if (index == 0) {
                head = new Node(element, null, null);
                rear = head;
                size++;
                return true;
            }
            throw new RuntimeException("you can only add new element in index 0!");
        }
        if (index < 0 || index > size) {
            // 判断 index 范围是否超出链表
            throw new RuntimeException("index out of range! ");
        }
        // 当插入位置是 头/尾 时，单独处理
        if (index == 0) {
            head = new Node(element, null, head);
            head.next.pre = head;
            size++;
            return true;
        }
        if (index == size) {
            rear = new Node(element, rear, null);
            rear.pre.next = rear;
            size++;
            return true;
        }
        // 当插入位置为中间节点时
        Node newNode = new Node(element, null, null);
        Node curr;
        if (index < size / 2) {
            // 如果index在链表前半，则从前向后遍历
            curr = head.next;
            int tag = 1;
            while (tag++ < index) {
                curr = curr.next;
            }
        } else {
            // 如果index在链表后半，则从后往前遍历
            curr = rear;
            int tag = size - 1;
            while (tag-- > index) {
                curr = curr.pre;
            }
        }
        // 遍历获得待插入节点的后一个节点
        newNode.pre = curr.pre;
        newNode.next = curr;
        curr.pre.next = newNode;
        curr.pre = newNode;
        size++;
        return true;
    }

    // delete element
    public boolean remove(String element) {
        // 判断当前链表是否为null，如果是，抛出异常
        if (isEmpty()) throw new RuntimeException("null list exception!!!");
        // 判断 element 是否为null
        if (element == null) {
            // 如果null，则使用 == 判断
            Node curr = head;
            while (curr != null) {
                if (curr.value == null) {
                    size--;
                    // 判断头尾节点情况
                    if (curr == head) {
                        head = curr.next;
                        head.pre = null;
                        return true;
                    }
                    if (curr == rear) {
                        rear = curr.pre;
                        rear.next = null;
                        return true;
                    } else {
                        curr.pre.next = curr.next;
                        curr.next.pre = curr.pre;
                        return true;
                    }
                }
                curr = curr.next;
            }
            return false;
        } else {
            // 如果非null，则 .equals() 判断
            Node curr = head;
            while (curr != null) {
                if (element.equals(curr.value)) {
                    size--;
                    // 判断头尾节点情况
                    if (curr == head) {
                        head = curr.next;
                        head.pre = null;
                        return true;
                    }
                    if (curr == rear) {
                        rear = curr.pre;
                        rear.next = null;
                        return true;
                    } else {
                        curr.pre.next = curr.next;
                        curr.next.pre = curr.pre;
                        return true;
                    }
                }
                curr = curr.next;
            }
            return false;
        }
    }

    // delete index
    public boolean remove(int index) {
        // 判断链表是否为null
        if (isEmpty()) throw new RuntimeException("null list exception!!!");
        // 判断index范围
        if (index < 0 || index > size - 1) throw new RuntimeException("index out of range!!!");
        // 判断头尾节点情况
        if (index == 0) {
            size--;
            head = head.next;
            head.pre = null;
            return true;
        }
        if (index == size - 1) {
            size--;
            rear = rear.pre;
            rear.next = null;
            return true;
        }
        // 非首尾节点情况
        int tag;
        Node curr;
        if (index < size / 2) {
            // 如果index在链表前半，则从前向后遍历
            tag = 1;
            curr = head.next;
            while (tag++ < index) {
                curr = curr.next;
            }
        } else {
            // 如果index在链表后半，则从后往前遍历
            tag = size - 2;
            curr = rear.pre;
            while (tag-- > index) {
                curr = curr.pre;
            }
        }
        // 经过遍历得到待删除节点
        size--;
        curr.pre.next = curr.next;
        curr.next.pre = curr.pre;
        return true;
    }

    // retrieve by element
    public boolean update(String oldValue, String newValue) {
        // 判断链表是否为null
        if (isEmpty()) throw new RuntimeException("null list exception!!!");
        // 判断 oldvalue 是否为null
        if (oldValue == null) {
            // 如果是，使用 == 比较
            Node curr = head;
            while (curr != null) {
                if (curr.value == null) {
                    curr.value = newValue;
                    return true;
                }
                curr = curr.next;
            }
            return false;
        } else {
            // 如果不是，使用 .equals() 比较
            Node curr = head;
            while (curr != null) {
                if (oldValue.equals(curr.value)) {
                    curr.value = newValue;
                    return true;
                }
                curr = curr.next;
            }
            return false;
        }
    }

    // retrieve by index
    public boolean update(int index, String newValue) {
        // 判断链表是否为null
        if (isEmpty()) throw new RuntimeException("null list exception!!!");
        // 判断index范围合法性
        if (index < 0 || index > size - 1) throw new RuntimeException("index out of range!!!");
        // 判断index范围
        int tag;
        Node curr;
        if (index < size / 2) {
            // 如果index在链表前半，则从前向后遍历
            curr = head;
            tag = 0;
            while (tag++ < index) {
                curr = curr.next;
            }
        } else {
            // 如果index在链表后半，则从后往前遍历
            curr = rear;
            tag = size - 1;
            while (tag-- > index) {
                curr = curr.pre;
            }
        }
        curr.value = newValue;
        return true;
    }

    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("MyDBList{");
        sb.append("head=").append(head);
        sb.append(", size=").append(size);
        sb.append('}');
        return sb.toString();
    }
}
